#include "td_rbtree.h"

TD_RBtree::TD_RBtree()
{
    null_node=new Node{-9999};
    null_node->color=Color::Black;
    null_node->left_chl=null_node->right_chl=null_node;
    fake_root=new Node{-9998,null_node,null_node,Color::Black};
}

TD_RBtree::~TD_RBtree()
{
    empty(fake_root->right_chl);
    delete null_node;
    delete  fake_root;
}

bool TD_RBtree::insert(int data_)
{
    current_insert=null_node;
    if(insert({fake_root->right_chl,fake_root,null_node,null_node},data_)){
        fake_root->right_chl->color=Color::Black;
        sort();
        return true;
    }
    return false;
}

void TD_RBtree::remove(int data_)
{
    current_remove=null_node;
    fake_root->color=Color::Red;
    if(remove({fake_root->right_chl,fake_root->left_chl,fake_root},data_)){
        int i=0;
        while (i<v.size()&&v[i]!=current_remove) {
            i++;
        }
        i++;
        while (i<v.size()) {
            v[i-1]=v[i];
            v[i-1]->w--;
            i++;
        }
        v.resize(v.size()-1);
//        delete current_remove;
    }
    fake_root->color=Color::Black;
}

void TD_RBtree::empty()
{
    v.clear();
    empty(fake_root->right_chl);
}

void TD_RBtree::empty(TD_RBtree::Node *&root_)
{
    if(root_!=null_node){
        empty(root_->left_chl);
        empty(root_->right_chl);
        delete root_;
        root_=null_node;
    }
}

void TD_RBtree::rotate_with_left(TD_RBtree::Node *&root_)
{
    Node * left=root_->left_chl;
    root_->left_chl=left->right_chl;
    left->right_chl=root_;
    root_=left;
}

void TD_RBtree::rotate_with_right(TD_RBtree::Node *&root_)
{
    Node * right=root_->right_chl;
    root_->right_chl=right->left_chl;
    right->left_chl=root_;
    root_=right;
}

void TD_RBtree::rotate_color_fix(I_Container c_)
{
    auto &[x,xp,xpp,xppp]=c_;
    if(xpp->left_chl==xp){
        if(xp->left_chl!=x)
            rotate_with_right(xp);
        rotate_with_left(xpp);
        xpp->color=Color::Black;
        xpp->right_chl->color=Color::Red;
    }else{
        if(xp->right_chl!=x)
            rotate_with_left(xp);
        rotate_with_right(xpp);
        xpp->color=Color::Black;
        xpp->left_chl->color=Color::Red;
    }
}

bool TD_RBtree::insert(I_Container c_, int data_)
{
    auto &[x,xp,xpp,xppp]=c_;
    if(x==null_node){
        current_insert=x=new Node{data_,null_node,null_node};
        if(x!=fake_root->right_chl&&xp->color==Color::Red)
            rotate_color_fix(c_);
        return true;
    }else{
        if(x->left_chl->color==Color::Red && x->right_chl->color==Color::Red){
            x!=fake_root->right_chl?x->color=Color::Red:x->color=Color::Black;
            x->left_chl->color=x->right_chl->color=Color::Black;
            if(xp->color==Color::Red){
                rotate_color_fix(c_);
                if(data_ < xpp->d){
                    return insert({xpp->left_chl,xpp,xppp,null_node},data_);
                }else if(data_ > xpp->d){
                    return insert({xpp->right_chl,xpp,xppp,null_node},data_);
                }else
                    return false;
            }
        }
        if(data_ < x->d){
            return insert({x->left_chl,x,xp,xpp},data_);
        }else if(data_ > x->d){
            return insert({x->right_chl,x,xp,xpp},data_);
        }else
            return false;
    }
}

bool TD_RBtree::remove(TD_RBtree::R_Container c_, int data_)
{
    auto & [x,t,xp]=c_;
    if(x==null_node)
        return false;
    if(x->color==Color::Red){       //单单这个分支真的，实现太烂了，太菜，想不到好方法
        //不需要处理，直接到下一步
        if(data_ < x->d){
            return remove({x->left_chl,x->right_chl,x},data_);
        }else if(data_ >x->d){
            return remove({x->right_chl,x->left_chl,x},data_);
        }else{
            if(x->left_chl==null_node&&x->right_chl==null_node){
                auto old=x;
                current_remove=old;
                x=null_node;
                delete old;
                return true;
            }else if(x->right_chl!=null_node){
                auto min=find<Min>(x->right_chl);
                x->d=min->d;
                return remove({x->right_chl,x->left_chl,x},x->d);
            }else{
                auto max=find<Max>(x->left_chl);
                x->d=max->d;
                return remove({x->left_chl,x->right_chl,x},x->d);
            }
        }
    }else if(x->left_chl->color==Color::Black&&x->right_chl->color==Color::Black){        //x有双黑孩子
        if(t->left_chl->color==Color::Black&&t->right_chl->color==Color::Black){        //t有双黑孩子
            x->color=Color::Red;
            t->color=Color::Red;
            xp->color=null_node->color=fake_root->right_chl->color=Color::Black;
        }else if(xp->right_chl==t){
            if(t->right_chl->color==Color::Black){
                rotate_with_left(t);
                rotate_with_right(xp);
                x->color=Color::Red;
                xp->left_chl->color=Color::Black;
            }else{
                rotate_with_right(xp);
                xp->color=Color::Red;
                fake_root->right_chl->color=Color::Black;       //..
                xp->left_chl->color=xp->right_chl->color=Color::Black;
                x->color=Color::Red;
            }
        }else{
            if(t->left_chl->color==Color::Black){
                rotate_with_right(t);
                rotate_with_left(xp);
                x->color=Color::Red;
                xp->right_chl->color=Color::Black;
            }else{
                rotate_with_left(xp);
                xp->color=Color::Red;
                fake_root->right_chl->color=Color::Black;   //..
                xp->left_chl->color=xp->right_chl->color=Color::Black;
                x->color=Color::Red;
            }
        }
        //处理结束，开始向对应子节点进行
        if(data_ < x->d){
            return remove({x->left_chl,x->right_chl,x},data_);
        }else if(data_ >x->d){
            return remove({x->right_chl,x->left_chl,x},data_);
        }else{
            if(x->left_chl==null_node&&x->right_chl==null_node){
                auto old=x;
                current_remove=old;
                x=null_node;
                delete old;
                return true;
            }else if(x->right_chl!=null_node){
                auto min=find<Min>(x->right_chl);
                x->d=min->d;
                return remove({x->right_chl,x->left_chl,x},x->d);
            }else{
                auto max=find<Max>(x->left_chl);
                x->d=max->d;
                return remove({x->left_chl,x->right_chl,x},x->d);
            }
        }
    }else {
        if(data_ <x->d){
            if(x->left_chl->color==Color::Black){
                auto new_t=x->right_chl;
                auto new_x=x;
                rotate_with_right(x);
                new_x->color=Color::Red;
                new_t->color=Color::Black;
                return remove({x->left_chl,x->right_chl,new_t->left_chl},data_);
            }else
                return remove({x->left_chl,x->right_chl,x},data_);
        }else if(data_ > x->d ){
            if(x->right_chl->color==Color::Black){
                auto new_t=x->left_chl;
                auto new_x=x;
                rotate_with_left(x);
                new_t->color=Color::Black;
                new_x->color=Color::Red;
                return remove({x->right_chl,x->left_chl,new_t->right_chl},data_);
            }else
                return remove({x->right_chl,x->left_chl,x},data_);
        }else{
            //null_node是黑节点，因此，叶子节点不会到此处
            //            if(x->left_chl==null_node&&x->right_chl==null_node){
            //                auto old=x;
            //                x=null_node;
            //                delete old;
            //            }else
            //下面的x子节点一定落到红节点，所以不用调整，直接推进到子节点
            if(x->right_chl!=null_node){
                auto min=find<Min>(x->right_chl);
                x->d=min->d;
                return remove({x->right_chl,x->left_chl,x},x->d);
            }else{
                auto max=find<Max>(x->left_chl);
                x->d=max->d;
                return remove({x->left_chl,x->right_chl,x},x->d);
            }
        }
    }

}

void TD_RBtree::sort()
{
    v.push_back(current_insert);
    auto temp =current_insert;
    int i=v.size()-1;
    for(;i>0&&temp->d<v[i-1]->d;i--){
        v[i]=v[i-1];
        v[i]->w=i;
    }
    v[i]=temp;
    v[i]->w=i;
}

void TD_RBtree::all_heights(TD_RBtree::Node *&root_, int cheight)
{
    if(root_!=null_node){
        root_->h=cheight;
        all_heights(root_->left_chl,cheight+1);
        all_heights(root_->right_chl,cheight+1);
    }
}

